//题目：
// 编写一个程序，通过填充空格来解决数独问题。
// 数独的解法需 遵循如下规则：
// 一行只能出现一次。
// 数字 1-9 在每一列只能出现一次。
// 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
// 数独部分空格内已填入了数字，空白格用 '.' 表示。
#include<iostream>
#include<vector>
#include<set>

using namespace std;
//代码:
class Solution 
{
    set<pair<int,int>> row;
    set<pair<int,int>> col;
    set<pair<pair<int,int>,int>> grid;
public:
    bool is_space_left(vector<char>& arr,int pos)
    {
        //判断arr数组红pos位置及后面是否存在字符'.'
        for(int i=pos;i<arr.size();i++)
            if(arr[i]=='.')return true;
        return false;
    }
    bool dfs(vector<vector<char>>& board,int pos,int col_init)
    {
        if(pos==board.size())  return true;//插入成功

        //先找到board[pos]行的空白格
        int col_pos=col_init;
        while(col_pos<board[pos].size() && board[pos][col_pos]!='.')col_pos++;

        if(col_pos>=board[pos].size())return dfs(board,pos+1,0);//这一行的一个空白格填充完了，进入下一行

        //判断数字1~9在board[pos][i]位置的有效性
        for(int num=1;num<=9;num++)
        {
            if(row.count({pos,num})==0 && col.count({col_pos,num})==0 && grid.count({{pos/3,col_pos/3},num})==0)
            {
                board[pos][col_pos]='0'+num;
                row.insert({pos,num});
                col.insert({col_pos,num});
                grid.insert({{pos/3,col_pos/3},num});
                //判断这一行的空白格是否已经全部填充完毕
                bool ret;
                if(is_space_left(board[pos],col_pos)==true)   
                    ret=dfs(board,pos,col_pos+1);//这一行还没填充完，要继续填充这一行,从i+1列开始
                else 
                    ret=dfs(board,pos+1,0);//这一行的一个空白格填充完了，进入下一行

                if(ret==true) return true;//剪枝
                //回溯
                board[pos][col_pos]='.';
                row.erase({pos,num});
                col.erase({col_pos,num});
                grid.erase({{pos/3,col_pos/3},num});       
            }
        }
        return false;
    }
    void solveSudoku(vector<vector<char>>& board) 
    {
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[i].size();j++)
            {
                if(board[i][j]!='.')
                {
                    row.insert({i,board[i][j]-'0'});
                    col.insert({j,board[i][j]-'0'});
                    grid.insert({{i/3,j/3},board[i][j]-'0'});
                }
            }
        }
        dfs(board,0,0);
    }
};